package leetcode_61_80;

import java.util.*;

public class setZeroes_73 {
    /**
     * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将0其所在行和列的所有元素都设为 0 。
     * 请使用 原地 算法。
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        /**
         * 先遍历，找到所有需要变为0的行和列存入set，然后对这些行进行赋值0
         * 避免行和列多次重复赋值0操作
         *
         * 1ms  48% ，还是不够快
         * 发现官解和我思路一样，懒得修改了
         */
        int row=matrix.length,col=matrix[0].length;
        Set<Integer> zeroRows=new HashSet<>();
        Set<Integer> zeroCols=new HashSet<>();
        for(int i=0;i<row;i++){       //行
            for(int j=0;j<col;j++){    //列
                if(matrix[i][j]==0){
                    zeroRows.add(i);
                    zeroCols.add(j);
                }
            }
        }
        for (int i:zeroRows)    //整行赋值0
              for(int j=0;j<col;j++)
                  matrix[i][j]=0;
        for (int i:zeroCols)     //整列赋值0
            for(int j=0;j<row;j++)
                matrix[j][i]=0;
        return;
    }
}
